package org.liaohailong.helloworld.array;

import java.util.Arrays;

/**
 * Author: liaohailong
 * Time: 2021/6/1 14:56
 * Describe:
 */
public class StringSolution {

    // LC 最长公共前缀
    public String longestCommonPrefix(String[] strs) {
        Arrays.sort(strs, (o1, o2) -> Integer.compare(o1.length(), o2.length()));
        String longStr = strs[strs.length - 1];
        int N = longStr.length();
        Character[] prefix = new Character[N];
        boolean end = false;
        for (int i = 0; i < N; i++) {
            if (end) break;

            for (String str : strs) {
                if (end) break;
                if (i < str.length()) {
                    char c = str.charAt(i);
                    if (prefix[i] == null) {
                        prefix[i] = c;
                    } else {
                        if (prefix[i] != c) {
                            prefix[i] = null;
                            end = true;
                        }
                    }
                } else end = true;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (Character character : prefix) {
            if (character == null) break;
            sb.append(character);
        }
        return sb.toString();
    }

    // LC 最长回文子串 - 暴力法 O(n3)
//    public String longestPalindrome(String s) {
//        char[] chars = s.toCharArray();
//        int N = chars.length;
//        int start = 0;
//        int end = N - 1;
//        boolean palindrome;
//
//        int findStart = 0;
//        int findEnd = 0;
//        while (true) {
//            palindrome = isPalindrome(chars, start, end);
//            if (palindrome) {
//                int count = end - start;
//                int findCount = findEnd - findStart;
//                if (findCount < count) {
//                    findStart = start;
//                    findEnd = end;
//                }
//            }
//
//            // 从左边慢慢左端，到右边界
//            start++;
//            if (start >= end) {
//                start = 0;
//                end--;
//                // 右边界也减完了，情况都遍历完了
//                if (start >= end) break;
//            }
//        }
//        return makeString(chars, findStart, findEnd);
//    }
//
//    private String makeString(char[] chars, int start, int end) {
//        StringBuilder sb = new StringBuilder();
//        for (int i = start; i <= end; i++) {
//            sb.append(chars[i]);
//        }
//        return sb.toString();
//    }
//
//    private boolean isPalindrome(char[] chars, int start, int end) {
//        while (start < end) {
//            if (chars[start] != chars[end]) return false;
//            start++;
//            end--;
//        }
//        return true;
//    }

    // LC 最长回文子串 - 动态规划 O(n2)
//    public String longestPalindrome(String s) {
//        char[] chars = s.toCharArray();
//        int N = s.length();
//        int end = N - 1;
//        int findStart = 0;
//        int findEnd = 0;
//        Boolean[][] dp = new Boolean[N][N];
//        for (int i = 0; i < end; i++) dp[i][i] = true;
//        // 右边界
//        for (int y = 1; y <= end; y++) {
//            for (int x = 0; x < y; x++) {
//                boolean is = _isPalindrome(chars, x, y, dp);
//                if (is) {
//                    dp[x][y] = true;
//                    int count = findEnd - findStart + 1;
//                    int _count = y - x + 1;
//                    if (count < _count) {
//                        findStart = x;
//                        findEnd = y;
//                    }
//                }
//            }
//        }
//        return s.substring(findStart, findEnd + 1);
//    }
//
//
//    private boolean _isPalindrome(char[] chars, int start, int end, Boolean[][] dp) {
//        Boolean is = dp[start][end];
//        if (is != null) return is;
//
//        if (start >= end) return true;
//        if (chars[start] == chars[end]) {
//            start++;
//            end--;
//            return _isPalindrome(chars, start, end, dp);
//        } else {
//            dp[start][end] = false;
//            return false;
//        }
//    }


    // LC 最长回文子串 - 中心扩散法 O(n2)
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i); // 奇数
            int len2 = expandAroundCenter(s, i, i + 1);// 偶数
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }


    // LC 翻转字符串里的单词
//    public String reverseWords(String s) {
//        char[] chars = s.toCharArray();
//        LinkedList<String> token = new LinkedList<>();
//        int start = -1;
//        int end = -1;
//        for (int i = 0; i < chars.length; i++) {
//            char c = chars[i];
//            if (c != ' ') {
//                if (start == -1) {
//                    start = i;
//                    end = start;
//                } else {
//                    end = i;
//                }
//            } else {
//                if (start != -1) {
//                    token.addFirst(s.substring(start, end + 1));
//                    start = -1;
//                    end = start;
//                }
//            }
//        }
//        // don't forget the last word
//        if (start != -1) token.addFirst(s.substring(start, end + 1));
//
//        StringBuilder sb = new StringBuilder();
//        for (String word : token) {
//            sb.append(word);
//            sb.append(" ");
//        }
//        if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
//        return sb.toString();
//    }

    // 字符串匹配相同字串 - 暴力法
    public int indexOf(String src, String dst) {
        if (dst.length() < 1) return 0;
        char[] srcChars = src.toCharArray();
        char[] dstChars = dst.toCharArray();

        int i = 0;
        int j = 0;
        while (i < srcChars.length && j < dstChars.length) {
            if (srcChars[i] == dstChars[j]) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j >= dstChars.length) return i - j;
        return -1;
    }

    /**
     * KMP 匹配字符串字串
     *
     * @param p 字串
     * @param s 总字符串
     * @return 匹配位置的下标，从0开始，返回-1表示未匹配到
     */
    public int match(String p, String s) {
        if (p.length() < 1) return 0;
        if (p.length() > s.length()) return -1;

        int[] next = buildNext(p); // 构造next表
        int m = s.length(), i = 0; // 文本串指针
        int n = p.length(), j = 0; // 模式串指针
        while (j < n && i < m) // 自左向右逐个比对字符
            if (0 > j || s.charAt(i) == p.charAt(j)) { // 若匹配，或p已移除最左侧
                i++;
                j++;
                // 则转下一字符
            } else j = next[j];// 模式串右移（注意：文本串不用回退）
        return j > 0 ? i - j : -1;
    }

    private int[] buildNext(String p) {
        int m = p.length();// "主" 串指针
        int j = 0;
        int[] N = new int[m]; // next表
        int t = N[0] = -1; // 模式串指针
        while (j < m - 1)
            if (0 > t || p.charAt(j) == p.charAt(t)) { // 匹配
                j++;
                t++;
                N[j] = t;
            } else t = N[t]; // 失配
        return N;
    }

    // LC 实现 strStr()
    public int strStr(String src, String dst) {
        if (dst.length() < 1) return 0;
        char[] srcChars = src.toCharArray();
        char[] dstChars = dst.toCharArray();

        int i = 0;
        int j = 0;
        while (i < srcChars.length && j < dstChars.length) {
            if (srcChars[i] == dstChars[j]) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j >= dstChars.length) return i - j;
        return -1;
    }

    // 数组拆分 I
    public int arrayPairSum(int[] nums) {
        if (nums.length < 1) return 0;
        if (nums.length <= 2) return Math.min(nums[0], nums[1]);

        Arrays.sort(nums);
        int slow = 0;
        int fast = 1;
        int total = 0;
        while (fast < nums.length) {
            total += Math.min(nums[slow], nums[fast]);
            slow += 2;
            fast += 2;
        }

        return total;
    }

    // LC 两数之和 II - 输入有序数组
//    public int[] twoSum(int[] numbers, int target) {
//        HashMap<Integer, Integer> hashMap = new HashMap<>();
//        for (int i = 0; i < numbers.length; i++) {
//            hashMap.put(numbers[i], i);
//        }
//        for (int i = 0; i < numbers.length; i++) {
//            int need = target - numbers[i];
//            Integer index = hashMap.get(need);
//            if (index != null) {
//                return new int[]{i + 1, index + 1};
//            }
//        }
//
//        return new int[]{1, 1};
//    }

    // LC 两数之和 II - 输入有序数组
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int add = numbers[left] + numbers[right];
            if (add == target) {
                return new int[]{left + 1, right + 1};
            } else if (add < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{1, 1};
    }

    // LC 移除元素
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        int fast = 0;
        boolean stop = false;
        while (slow < nums.length && fast < nums.length && !stop) {
            if (nums[slow] != val) {
                slow++;
            } else {
                fast = slow + 1;
                while (fast < nums.length) {
                    if (nums[fast] != val) {
                        int temp = nums[slow];
                        nums[slow] = nums[fast];
                        nums[fast] = temp;
                        if (fast == nums.length - 1) {
                            stop = true; // 已经全部找完了
                            slow++;
                        }
                        break;
                    } else fast++;
                }
            }
        }
        return slow;
    }

    // LC 最大连续1的个数
    public int findMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0;
        int count = 0;
        for (int num : nums) {
            if (num == 1) {
                count++;
            } else {
                if (maxCount < count) maxCount = count;
                count = 0;
            }
        }
        if (maxCount < count) maxCount = count;
        return maxCount;
    }

    // LC 长度最小的子数组
//    public int minSubArrayLen(int target, int[] nums) {
//        int left = 0;
//        int right = 0;
//        int min = -1;
//        int total = 0;
//        while (left <= right && left < nums.length && right < nums.length) {
//            total += nums[right];
//            if (total < target)
//                right++;
//            else {
//                int count = right - left + 1;
//                min = min == -1 ? count : Math.min(min, count);
//                total = 0;
//                left++;
//                right = left;
//                if (min <= 1) break;
//            }
//        }
//        return min == -1 ? 0 : min;
//    }

    // LC 长度最小的子数组
//    public int minSubArrayLen(int target, int[] nums) {
//        int min = -1;
//
//        int depth;
//        int total;
//        for (int i = 0; i < nums.length; i++) {
//            depth = 1;
//            total = nums[i];
//            if (total >= target) {
//                min = depth;
//            } else {
//                for (int j = i + 1; j < nums.length; j++) {
//                    depth++;
//                    total += nums[j];
//                    if (total >= target) {
//                        min = min == -1 ? depth : Math.min(min, depth);
//                        break;
//                    }
//                }
//            }
//        }
//        return Math.max(0, min);
//    }

    // LC 长度最小的子数组 - 收缩法
    public int minSubArrayLen(int target, int[] nums) {
        int slow = 0;
        int fast = -1;

        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            total += nums[i];
            if (total >= target) {
                fast = i;
                break;
            }
        }
        // 全部加起来都不够
        if (fast == -1) return 0;

        int min = fast - slow;
        if (fast == nums.length - 1) {
            // 尝试左缩进
            int temp = total;
            while (true) {
                temp -= nums[slow];
                if (temp >= target) {
                    slow++;
                } else break;
            }
            min = Math.min(min, fast - slow);
        } else {
            while (true) {
                fast++;

                if (fast < nums.length) {
                    // 尝试右扩展
                    total += nums[fast];
                    // 尝试左缩进
                    int temp = total;
                    while (true) {
                        temp -= nums[slow];
                        if (temp >= target) {
                            slow++;
                            total = temp;
                        } else break;
                    }
                    min = Math.min(min, fast - slow);
                } else break;
            }
        }

        return min + 1;
    }

    // LC 反转字符串中的单词 III
    public String reverseWords(String s) {
        char[] array = s.toCharArray();
        int start = -1;
        int end = -1;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == ' ') {
                if (start != -1) {
                    _reverseWords(array, start, end);
                    start = -1;
                    end = -1;
                }
            } else {
                if (start == -1) {
                    start = i;
                    end = i;
                } else {
                    end++;
                }
            }
        }
        // last but not least
        if (start != -1) _reverseWords(array, start, end);

        return String.valueOf(array);
    }

    private void _reverseWords(char[] array, int left, int right) {
        while (left < right) {
            char temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left++;
            right--;
        }
    }

    // LC 寻找旋转排序数组中的最小值
    public int findMin(int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num < min) min = num;
        }
        return min;
    }
//    // LC 寻找旋转排序数组中的最小值
//    public int findMin(int[] nums) {
//        return _findMin(nums, 0, nums.length - 1);
//    }
//
//    private int _findMin(int[] nums, int left, int right) {
//        int mid = left + (right - left) / 2;
//        if (mid == left) return Math.min(nums[left], nums[right]);
//        int rightMin = Integer.MAX_VALUE;
//        while (left < right) {
//            mid = left + (right - left) / 2;
//            // 比较右侧
//            if (nums[mid] < nums[mid + 1]) {
//                int _rightMin = _findMin(nums, mid, right);
//                rightMin = Math.min(_rightMin, rightMin);
//                // 已经找到最左边，这个就是最小值
//                if (mid == 0) {
//                    return Math.min(nums[mid], rightMin);
//                }
//                // 比较左边
//                else if (nums[mid - 1] < nums[mid]) {
//                    // 左边比自己小，右边比自己大，那么继续往左边开始找mid
//                    right = mid;
//                } else {
//                    // 命中，自己比左小，必为最小值
//                    return nums[mid];
//                }
//            } else {
//                // 命中，右边比左小，必为最小值
//                return nums[mid + 1];
//            }
//        }
//
//        return Math.min(nums[mid], rightMin);
//    }

    // LC 删除排序数组中的重复项
//    public int removeDuplicates(int[] nums) {
//        int first = 0;
//        int last = nums.length - 1;
//        while (first < last) {
//            int firstOne = nums[first];
//            int next = first + 1;
//            int nextOne = nums[next];
//            if (firstOne != nextOne) {
//                // 未重复，移动first指针
//                first++;
//            } else {
//                // 发现相同，开始移动位置
//                // 把next移到nums的尾部
//                while (next + 1 < nums.length) {
//                    nums[next] = nums[next + 1];
//                    next++;
//                }
////                nums[nums.length - 1] = nextOne;
//                // 原来的last收缩
//                last--;
//            }
//        }
//        return first + 1;
//    }

    // LC 删除排序数组中的重复项
    public int removeDuplicates(int[] nums) {
        if (nums == null && nums.length == 0) {
            return 0;
        }
        int left = 0;
        for (int right = 1; right < nums.length; right++) {
            if (nums[right] != nums[left]) {
                left++;
                nums[left] = nums[right];
            }
        }
        return left + 1;
    }

    // LC 移动零
//    public void moveZeroes(int[] nums) {
//        int first = -1;
//        int last = nums.length - 1;
//        while (first < last) {
//            int next = first + 1;
//            int nextOne = nums[next];
//            if (nextOne != 0) {
//                // 未重复，移动first指针
//                first++;
//            } else {
//                // 发现相同，开始移动位置
//                // 把next移到nums的尾部
//                while (next + 1 < nums.length) {
//                    nums[next] = nums[next + 1];
//                    next++;
//                }
//                nums[nums.length - 1] = nextOne;
//                // 原来的last收缩
//                last--;
//            }
//        }
//    }

    // LC 移动零
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
        }
    }
}
